October 31, 2025
A network is scale-free if the tail of the degree distribution follows a power-law.
\[ \Pr(K>k) = \bar F(k) \sim k^{-\gamma} \]
Scale-free Degree Distribution — Orginal scale
Scale-free Degree Distribution — Log scale
There has been a heated debate over the presence of scale-free networks in reality.
Zipf-Polylog
\[ f(k) \propto x^{-\alpha} \theta^x, \qquad x=1, 2, \ldots, u \]
Integer Generalised Pareto
\[ F(k)= 1-\left(1+\frac{\xi(k-u)}{\sigma +\xi u}\right)_+^{-1/\xi}, \qquad x=u+1,\ldots \]
Using this model @Lee24 found that networks often have a heavy tail but not quite as heavy as implied by the body.
Many use scale-freeness of a network to justify the mechanics behind the network’s growth.
Preferential Attachment (rich-get-richer) \(\Rightarrow\) Power-law degree distribution
but
Power-law degree distribution \(\nRightarrow\) Preferential Attachment (rich-get-richer)
This is fairly common as modelling the degrees does not generally inform the network growth.
Example
\[ \pi_i = \left. k_i \middle/ \sum k_j \right. \] where \(k_i\) is degree of node \(i\).
Results in a power-law degree distribution
\[ \bar F(k)\sim k^{-2} \]
Example
\[ \pi_i = \left. b(k_i) \middle/ \sum b(k_j) \right. \] where \(k_i\) is degree of node \(i\).
How do we study the degree distribution of this?
Consider a CTBP \(\zeta(t)\) driven by Markovian pure birth process
\[ \Pr(\zeta(t+\text{d}t) = k+1 | \zeta(t) =k) = b(k) \text{d}t + o(\text{d}t) \]
Construct tree \(\Upsilon(t)\) determined by \(\zeta(t)\), where each node in the tree has birth rate \(b(\text{deg}(x,\Upsilon(t)))\).
Then the tail of the limiting degree distribution is:
\[ \bar F(k) = \lim_{t\rightarrow \infty} \frac{\sum_{x\in\Upsilon(t)}\mathbb I \left\{\text{deg}(x, \Upsilon(t))_{\downarrow x}>k\right\}}{ \sum_{x\in\Upsilon(t)} \mathbb I \left\{\text{deg}(x, \Upsilon(t))_{\downarrow x}\ge 0\right\}\right\}} \]
Now applying a result from [Rudas et al.]
For a characteristic \(\phi\) of the tree \(\Upsilon(t)\):
\[ \lim_{t\rightarrow\infty} \frac{1}{\left|\Upsilon(r)\right|}\sum_{x\in\Upsilon(t)}\phi(\Upsilon(t)_{\downarrow x}) = \lambda^* \int_0^\infty e^{-\lambda^*}\mathbb E \left[\phi(\Upsilon(t))\right]\text{d}t \]
\[ \bar F(k) = \frac{\int_0^\infty e^{-\lambda^*t}\mathbb I \left\{\text{deg}(x, \Upsilon(t))_{\downarrow x}>k\right\}\text{d}t }{\int_0^\infty e^{-\lambda^* t} \text{d}t} = \prod_{i=0}^k \frac{b(i)}{\lambda^* + b(i)},\quad k=0,1,2, \ldots \]
We want to pay careful attention to the extreme values
Studies of empirical degrees often use methods from continuous extremes
As this is a discrete distribution we need some new machinery.
Frechet (heavy tailed)
\[ \bar F(x) = x^{-\gamma} L(x) \] e.g. Pareto, Cauchy, Lévy
Gumbel (light-tailed)
\[ \lim_{x\rightarrow\infty}\frac{\bar F (x + t a(x))}{\bar F(x)}= e^{-t} \] e.g. Exponential, Normal, Gamma
All continuous distributions with infinite right endpoint fall into one of these.
Many discrete distributions don’t satisfy the conditions to belong to an MDA
[Shimura] uses the following quantity to categorise discrete distributions \[ \Omega(F, k) = \left(\log \frac{\bar F(k+1)}{ \bar F(k+2)}\right)^{-1} - \left(\log \frac{\bar F(k)}{ \bar F(k+1)}\right)^{-1} \]
Frechet
\[ \lim_{k\rightarrow\infty} \Omega(F,k) = 1/\alpha \] and \[ \lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} = 1 \]
Recoverable to Gumbel
\[ \lim_{k\rightarrow\infty} \Omega(F,k) = 0 \] and \[ \lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} \neq 1 \]
Gumbel
\[ \lim_{k\rightarrow\infty} \Omega(F,k) = 0 \] and \[ \lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} = 1 \]
Now we can use the limiting survival function of a GPA model to show that:
\[ \lim_{k\rightarrow\infty} \Omega(F,k)= \begin{cases} \lim_{k\rightarrow \infty}\frac{b(k+1)-b(k)}{\lambda^*}, &\text{when } b(k) \rightarrow \infty\\ 0, &\text{otherwise} \end{cases} \]
Barabasi-Albert (BA) \[ b(k) = k+1 \] \[ \lim_{k\rightarrow\infty} \Omega(F,k) = 1/\lambda^* = 1/2 \] \[ \lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} = 1 \] Frechet, with index 2
Uniform \[ b(k) = c \] \[ \lim_{k\rightarrow\infty} \Omega(F,k) = 1/\lambda^* = 0 \] \[ \lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} = 0 \] Recoverable to Gumbel
Polynomial \[ b(k) = (k+1)^\alpha \] \[ \lim_{k\rightarrow\infty} \Omega(F,k) = 1/\lambda^* = 0 \] \[ \lim_{k\rightarrow\infty} \frac{\bar F(k+1)}{\bar F(k)} = 1 \] Gumbel
\[ \lim_{k\rightarrow\infty} \Omega(F,k)= \begin{cases} \lim_{k\rightarrow \infty}\frac{b(k+1)-b(k)}{\lambda^*}, &\text{when } b(k) \rightarrow \infty\\ 0, &\text{otherwise} \end{cases} \]
We require something that is eventually linear but is flexible enough for real networks
Barabasi-Albert \[ b(k) = k+1 \]
Proposed Model \[ b(k) = \begin{cases} k^\alpha + \varepsilon, &k\le k_0\\ k_0^\alpha + \varepsilon + \beta(k-k_0), &k>k_0 \end{cases} \]
\[ \bar F(k) = \frac{2}{(k+2)(k+3)} \]
\[ \bar F(k) = \begin{cases} \prod_{i=0}^{k}\frac{i^\alpha + \varepsilon}{\lambda^*+i^\alpha + \varepsilon},&k\le k_0,\\ \left(\prod_{i=0}^{k_0-1}\frac{i^\alpha + \varepsilon}{\lambda^*+i^\alpha + \varepsilon}\right)\frac{\Gamma(\lambda^*+k_0^\alpha + \varepsilon)/\beta)}{\Gamma\left((k_0^\alpha + \varepsilon)/\beta\right)} \frac{\Gamma\left(k-k_0 + 1 +\frac{k_0^\alpha + \varepsilon}{\beta}\right)}{\Gamma\left(k-k_0 + 1 +\frac{\lambda^* +k_0^\alpha + \varepsilon}{\beta}\right)},&k > k_0, \end{cases} \]
% heat map plot
\[ \lim_{k\rightarrow\infty} \Omega(F, k) = \beta / \lambda^*, \qquad \lim_{k\rightarrow\infty} \bar F(k+1)/ \bar F(k) = 1 \]
All limiting degree distributions produces by this model are Frechet with tail-index \(\lambda^*/\beta\).
We can find that: \[ \bar F(k) \begin{cases} =\prod_{i=0}^{k}\frac{i^\alpha + \varepsilon}{\lambda^*+i^\alpha + \varepsilon},&k\le k_0,\\ \approx \left(\prod_{i=0}^{k_0}\frac{i^\alpha + \varepsilon}{\lambda^* + i^\alpha + \varepsilon}\right)\left(\frac{\beta(k-k_0)}{k_0^{\alpha}+\varepsilon+\beta} + 1\right)^{-\lambda^{*}/\beta},&k > k_0, \end{cases} \]
that is, conditional degree distribution is approximated by:
\[ \text{IGP}\left(\frac{\beta}{\lambda^*}, \frac{k_0^\alpha + \varepsilon+\beta}{\lambda^*},k_0\right) \]
a distribution used by [Lee] for modelling network degrees.
Unfortunately we can’t go from the IGP fit to the model parameters.
\[ \begin{aligned} L(\pmb n | \pmb \theta,l) = &\left(\frac{\lambda^*}{\lambda^*+\varepsilon}\right)^{n_0}\left(\prod_{j=l}^{k_0-1}\frac{j^\alpha +\varepsilon}{\lambda^* + j^\alpha +\varepsilon}\right)^{\left(\sum_{i\ge k_0}n_{i}\right)} \\ &\times \prod_{l \le i<k_0}\left(\frac{\lambda^*}{\lambda^* +i^\alpha + \varepsilon } \prod_{j=l}^{k_0-1}\frac{j^\alpha + \varepsilon}{\lambda^* + j^\alpha + \varepsilon}\right)^{n_i}\\ &\times \prod_{i\ge k_0}\left(\frac{\text{B}(i-k_0 + (k_0^\alpha + \varepsilon)/\beta,1+\lambda^*/\beta)}{\text{B}((k_0^\alpha + \varepsilon)/\beta,\lambda^*/\beta)}\right)^{n_i}, \end{aligned} \]
\[\begin{align*} \alpha&\sim \text{Gamma}(1,0.01),\\ \beta &\sim \text{Gamma}(1,0.01),\\ k_0 &\sim \text{U}(1,10,000),\\ \varepsilon &\sim \text{Gamma(1,0.01)}, \end{align*}\]
Now we use an adaptive Metroplis-Hastings to obtain posterior samples
%show model fitting the degree distribution well
Internet
Flights
Proteins
Data sourced from Network Data Repository[@nr]
We will fit the model and compare it to the mixture model.
Theory based on trees, which real networks rarely are
Only consider degrees in the snapshot
Assume a fairly restrictive model (pure birth)
Look beyond just the degrees
Incorporate more complex behaviour into the growth model
Extend theory beyond that of trees
Beyond the Descriptive Modelling of Degrees - Thomas Boughen